<?php

class GrammarAnalyzer {
    
    /**
     * @var array<Token>
     */
    private $tokenList;
    
    /**
     * 
     * @param int $tokenIndex
     */
    private $tokenIndex;
    
    public function __construct($tokenList) {
        $this->tokenList = $tokenList;
        $this->tokenIndex = 0;
    }
    
    public function run(){
        $tokenCount = count($this->tokenList);
        
        // 开始语法分析
        $tree = $this->program();
        
        return $tree;
    }
    
    /**
     * @see ECMA-262 5rd chapter 14
     */
    private function program(){
        // 创建语法树的根
        $root = new Root();
        
        for(;;){
            
            // 到达程序末尾
            $currentToken = $this->getCurrentToken();
            if($currentToken == NULL){
                break;
            }
            
            $node = $this->sourceElement();
            $root->addChildToBack($node);
            $node->setParent($root);
        }
        
        return $root;
    }
    
    /**
     * @see ECMA-262 5rd chapter 14
     */
    private function sourceElement(){
        $currentToken = $this->getCurrentToken();
        $tokenType = $currentToken->getTokenType();
        $tokenLiteral = $currentToken->getTokenLiteral();
        
        if($tokenType == Token::IdentifierName && $tokenLiteral == 'function'){
            $node = $this->functionDeclaration();
        }
        else{
            $node = $this->statement();
        }
        
        return $node;
    }
    
    /**
     * @see ECMA-262 5rd chapter 13
     * 
     * FunctionDeclaration :
     *     function Identifier ( FormalParameterList ) { FunctionBody }
     */
    private function functionDeclaration(){
        $currentToken = $this->getCurrentToken();
        $tokenType = $currentToken->getTokenType();
        $tokenLiteral = $currentToken->getTokenLiteral();
        
        if($tokenType == Token::IdentifierName && $tokenLiteral == 'function'){
            // 消耗掉token:function
            $this->consumeCurrentToken();
            
            // 消耗掉token:IdentifierName
            $idToken = $this->getCurrentToken();
            if($idToken->getTokenType() == Token::IdentifierName){
                $functionName = $this->createIdNode($idToken);
                $this->consumeCurrentToken();
            }
            else{
                $functionName = null; // 匿名函数
            }
            
            // 消耗掉token:(
            $punctuatorToken = $this->getCurrentToken();
            if( ($punctuatorToken->getTokenType()) != Token::Punctuator_LeftParenthesis ){
                throw new Exception(ERR_MSG_GRAMMAR_1, ERR_CODE_GRAMMAR_1); 
            }
            $this->consumeCurrentToken();
            
            // 解析function params
            $formalParamList = $this->parseFormalParamList();
            
            // 消耗掉token:)
            $punctuatorToken = $this->getCurrentToken();
            if( ($punctuatorToken->getTokenType()) != Token::Punctuator_RightParenthesis ){
                throw new Exception(ERR_MSG_GRAMMAR_1, ERR_CODE_GRAMMAR_1); 
            }
            $this->consumeCurrentToken();
            
            // 消耗掉token:{
            $punctuatorToken = $this->getCurrentToken();
            if( ($punctuatorToken->getTokenType()) != Token::Punctuator_LeftBrace ){
                throw new Exception(ERR_MSG_GRAMMAR_1, ERR_CODE_GRAMMAR_1); 
            }
            $this->consumeCurrentToken();
            
            // 解析function body
            $functionBody = $this->parseFunctionBody();
            
            // 消耗掉token:}
            $punctuatorToken = $this->getCurrentToken();
            if( ($punctuatorToken->getTokenType()) != Token::Punctuator_RightBrace ){
                throw new Exception(ERR_MSG_GRAMMAR_1, ERR_CODE_GRAMMAR_1); 
            }
            $this->consumeCurrentToken();
            
            $functionNode = $this->createFunctionNode($functionName, $formalParamList, $functionBody);
            return $functionNode;
        }
        else{
            throw new Exception(ERR_MSG_GRAMMAR_1, ERR_CODE_GRAMMAR_1); 
        }
    }
    
    /**
     * 解析参数列表
     * 
     * @see ECMA-262 5rd chapter 13
     */
    private function parseFormalParamList(){
        $paramsList = array();
        
        // 第一个token
        $token = $this->getCurrentToken();
        
        // 为右括号,则退出
        if($token->getTokenType() == Token::Punctuator_RightParenthesis){
            return $paramsList;
        }
        // 为ID
        else if( $token->getTokenType() == Token::IdentifierName ){
            $paramsList[] = $this->createIdNode($token);
            $this->consumeCurrentToken();
        }
        // 不可能有其他情况
        else{
            throw new Exception(ERR_MSG_GRAMMAR_1, ERR_CODE_GRAMMAR_1); 
        }
        
        while( ($token = $this->getCurrentToken()) != NULL ) {
            if($token->getTokenType() == Token::Punctuator_Comma){
                //获取一下个ID
                $this->consumeCurrentToken();
                $idToken = $this->getCurrentToken();
                $paramsList[] = $this->createIdNode($idToken);
                $this->consumeCurrentToken();
            }
            else if($token->getTokenType() == Token::Punctuator_RightParenthesis){
                return $paramsList;
            }
            else{
                throw new Exception(ERR_MSG_GRAMMAR_1, ERR_CODE_GRAMMAR_1); 
            }
        }
        
        return $paramsList;
    }
    
    /**
     * 解析函数体
     * 
     * @see ECMA-262 5rd chapter 13
     */
    private function parseFunctionBody(){
        
        $block = new BlockNode();
        
        for (;;) {
            $currentToken = $this->getCurrentToken();
            if($currentToken == NULL){
                throw new Exception(ERR_MSG_GRAMMAR_1, ERR_CODE_GRAMMAR_1); 
            }
            
            $tokenType = $currentToken->getTokenType();
            $tokenLiteral = $currentToken->getTokenLiteral();
            
            if($tokenType == Token::COMMENT ){
                continue;
            }
            if($tokenType == Token::Punctuator_RightBrace){
                break;
            }
            
            $statement = $this->sourceElement();
            $block->addStatement($statement);
        }
        
        return $block;
    }
    
    /**
     * @see ECMA-262 5rd chapter 12
     */
    private function statement(){
        $currentToken = $this->getCurrentToken();
        $tokenType = $currentToken->getTokenType();
        $tokenLiteral = $currentToken->getTokenLiteral();
        
        // Block
        if($tokenType == Token::Punctuator_LeftBrace){
            $statement = $this->block();
        }
        // VariableStatement
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'var'){
            $statement = $this->variableStatement();
        }
        // EmptyStatement 
        else if($tokenType == Token::Punctuator_Semicolon){
            $statement = $this->emptyStatement();
        }
        // IfStatement 
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'if'){
            $statement = $this->ifStatement();
        }
        // IterationStatement
        else if($tokenType == Token::IdentifierName && ( $tokenLiteral == 'do' || $tokenLiteral == 'while' || $tokenLiteral == 'for')){
            $statement = $this->iterationStatement();
        }
        // ContinueStatement
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'continue'){
            $statement = $this->continueStatement();
        }
        // BreakStatement
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'break'){
            $statement = $this->breakStatement();
        }
        // ReturnStatement 
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'return'){
            $statement = $this->returnStatement();
        }
        // WithStatement 
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'with'){
            $statement = $this->withStatement();
        }
        // SwitchStatement
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'switch'){
            $statement = $this->switchStatement();
        }
        // ThrowStatement
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'throw'){
            $statement = $this->throwStatement();
        }
        // TryStatement
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'try'){
            $statement = $this->tryStatement();
        }
        // DebuggerStatement
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'debugger'){
            $statement = $this->debuggerStatement();
        }
        // LabelledStatement || ExpressionStatement 
        else{
            $nextToken = $this->getNextToken();
            if($tokenType == Token::IdentifierName && ($nextToken->getTokenType() == Token::Punctuator_Colon)){
                $statement = $this->labelledStatement();
            }
            else{
                $statement = $this->expressionStatement();
            }
        }
        
        return $statement;
    }
    
    /**
     * 解析block语句
     * 
     * @see ECMA-262 5rd chapter 12.1
     */
    private function block(){
        // 消耗掉token:{
        $currentToken = $this->getCurrentToken();
        if( ($currentToken->getTokenType()) != Token::Punctuator_LeftBrace ){
            throw new Exception(ERR_MSG_GRAMMAR_2, ERR_CODE_GRAMMAR_2); 
        }
        $this->consumeCurrentToken();
        
        // 解析statementList
        $statementList = $this->statementList();
        
        // 消耗掉token:}
        $punctuatorToken = $this->getCurrentToken();
        if( ($punctuatorToken->getTokenType()) != Token::Punctuator_RightBrace ){
            throw new Exception(ERR_MSG_GRAMMAR_2, ERR_CODE_GRAMMAR_2); 
        }
        $this->consumeCurrentToken();
        
        // block
        $block = new BlockNode();
        foreach ($statementList as $statement) {
            $block->addStatement($statement);
        }
        
        return $block;
    }
    
    /**
     * @see ECMA-262 5rd chapter 12.1
     */
    private function statementList(){
        $statementList = array();
        
        for (;;){
            $currentToken = $this->getCurrentToken();
            $tokenType = $currentToken->getTokenType();
            $tokenLiteral = $currentToken->getTokenLiteral();
            if($tokenType == Token::COMMENT){
                continue;
            }
            else if($tokenType == Token::Punctuator_RightBrace){
                break;
            }
            else {
                $statement = $this->statement();
            }
            
            $statementList []= $statement;
        }
        
        return $statementList;
    }
    
    /**
     * 解析var语句
     * 
     * @see ECMA-262 5rd chapter 12.2
     */
    private function variableStatement(){
        // 消耗掉var
        $currentToken = $this->getCurrentToken();
        $tokenType = $currentToken->getTokenType();
        $tokenLiteral = $currentToken->getTokenLiteral();
        if( !($tokenType == Token::IdentifierName && $tokenLiteral == 'var') ){
            throw new Exception(ERR_MSG_GRAMMAR_3, ERR_CODE_GRAMMAR_3); 
        }
        $this->consumeCurrentToken();
        
        // 解析variableDeclarationList
        $variableDeclarationList = $this->variableDeclarationList();
        
        // 消耗掉;
        $punctuatorToken = $this->getCurrentToken();
        if( ($punctuatorToken->getTokenType()) != Token::Punctuator_Semicolon ){
            throw new Exception(ERR_MSG_GRAMMAR_3, ERR_CODE_GRAMMAR_3); 
        }
        $this->consumeCurrentToken();
        
        // variableStatement
        $variableStatement = new VariableStatementNode();
        foreach ($variableDeclarationList as $variableDeclaration){
            $variableStatement->addVariable($variableDeclaration);
        }
        return $variableStatement;
    }
    
    /**
     * @see ECMA-262 5rd chapter 12.2
     */
    private function variableDeclarationList(){
        $variableDeclarationList = array();
        for (;;){
            // 逐个分析VariableDeclaration
            $variableDeclaration = $this->variableDeclaration();
            $variableDeclarationList []= $variableDeclaration;
            
            // 如果不是','则退出
            $punctuatorToken = $this->getCurrentToken();
            if( ($punctuatorToken->getTokenType()) != Token::Punctuator_Comma ){
                break;
            }
            else{
                $this->consumeCurrentToken();
            }
        }
        
        return $variableDeclarationList;
    }
    
    /**
     * @see ECMA-262 5rd chapter 12.2
     */
    private function variableDeclaration(){
        // Identifier
        $currentToken = $this->getCurrentToken();
        if(($currentToken->getTokenType()) != Token::IdentifierName ){
            throw new Exception(ERR_MSG_GRAMMAR_3, ERR_CODE_GRAMMAR_3); 
        }
        $variableName = $this->createIdNode($currentToken);
        $this->consumeCurrentToken();
        
        // 判断是否有initializer
        $punctuatorToken = $this->getCurrentToken();
        if( $punctuatorToken->getTokenType() == Token::Punctuator_Equal ){
            $this->consumeCurrentToken();
            $initializer = $this->assignmentExpression();
        }
        else{
            $initializer = NULL;
        }
        
        $variableDeclaration = new VariableDeclarationNode();
        $variableDeclaration->variableName = $variableName;
        $variableDeclaration->initializer = $initializer;
        return $variableDeclaration;
    }
    
    /**
     * 解析empty语句
     * 
     * @see ECMA-262 5rd chapter 12.3
     */
    private function emptyStatement(){
        // 消耗掉;
        $punctuatorToken = $this->getCurrentToken();
        if( ($punctuatorToken->getTokenType()) != Token::Punctuator_Semicolon ){
            throw new Exception(ERR_MSG_GRAMMAR_4, ERR_CODE_GRAMMAR_4);
        }
        $this->consumeCurrentToken();
        
        return new EmptyStatementNode();
    }
    
    /**
     * 解析if语句
     * 
     * @see ECMA-262 5rd chapter 12.5
     */
    private function ifStatement(){
        // 消耗掉token:if
        $currentToken = $this->getCurrentToken();
        $tokenType = $currentToken->getTokenType();
        $tokenLiteral = $currentToken->getTokenLiteral();
        if( !($tokenType == Token::IdentifierName && $tokenLiteral == 'if')){
            throw new Exception(ERR_MSG_GRAMMAR_5, ERR_CODE_GRAMMAR_5); 
        }
        $this->consumeCurrentToken();
        
        // 消耗掉token:(
        $punctuatorToken = $this->getCurrentToken();
        if( ($punctuatorToken->getTokenType()) != Token::Punctuator_LeftParenthesis ){
            throw new Exception(ERR_MSG_GRAMMAR_5, ERR_CODE_GRAMMAR_5); 
        }
        $this->consumeCurrentToken();
        
        // 解析条件
        $expression = $this->expression();
        
        // 消耗掉token:)
        $punctuatorToken = $this->getCurrentToken();
        if( ($punctuatorToken->getTokenType()) != Token::Punctuator_RightParenthesis ){
            throw new Exception(ERR_MSG_GRAMMAR_5, ERR_CODE_GRAMMAR_5); 
        }
        $this->consumeCurrentToken();
        
        // 解析 if true的时候 statement
        $trueStatement = $this->statement();
        
        // 判断是否有else
        $idToken = $this->getCurrentToken();
        $idTokenType = $idToken->getTokenType();
        $IdTokenLiteral = $idToken->getTokenLiteral();
        if($idTokenType == Token::IdentifierName && $IdTokenLiteral == 'else'){
            $this->consumeCurrentToken();
            $falseStatement = $this->statement();
        }else{
            $falseStatement = NULL;
        }
        
        $ifStatement = new IfStatementNode();
        $ifStatement->condition = $expression;
        $ifStatement->trueStatement = $trueStatement;
        $ifStatement->falseStatement = $falseStatement;
        return $ifStatement;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.14
     */
    private function expression(){
        $expression = new Expression();
        
        for (;;){
            // 逐个分析assignmentExpression
            $assignmentExpression = $this->assignmentExpression();
            $expression->addExpression($assignmentExpression);
            
            // 如果不是','则退出
            $punctuatorToken = $this->getCurrentToken();
            if( ($punctuatorToken->getTokenType()) != Token::Punctuator_Comma ){
                break;
            }
            else{
                $this->consumeCurrentToken();
            }
        }
        
        return $expression;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.13
     * 
     * AssignmentExpression : 
     *     ConditionalExpression 
     *     LeftHandSideExpression AssignmentOperator AssignmentExpression 
     * AssignmentOperator :  one of  
     *     =  *=  /=  %= +=  -= <<= >>= >>>= &= ^= |= 
     */
    private function assignmentExpression(){
        // 先尝试leftHandSideExpression
        $hasAssign = TRUE;
        try{
            $leftHandSideExpression = $this->leftHandSideExpression();
        }
        catch (Exception $e){
            $hasAssign = FALSE;
        }
        
        if($hasAssign){
            // AssignmentOperator
            $token = $this->getCurrentToken();
            if( $token->getTokenType() == Token::Punctuator_Equal 
             || $token->getTokenType() == Token::Punctuator_AsteriskEqual 
             || $token->getTokenType() == Token::Punctuator_DivisionEqual
             || $token->getTokenType() == Token::Punctuator_PercentEqual
             || $token->getTokenType() == Token::Punctuator_AddEqual
             || $token->getTokenType() == Token::Punctuator_MinusEqual
             || $token->getTokenType() == Token::Punctuator_LessLessEqual
             || $token->getTokenType() == Token::Punctuator_MoreMoreEqual
             || $token->getTokenType() == Token::Punctuator_MoreMoreMoreEqual
             || $token->getTokenType() == Token::Punctuator_AndEqual
             || $token->getTokenType() == Token::Punctuator_OrEqual
             || $token->getTokenType() == Token::Punctuator_ExclusiveOrEqual)
            {
                $this->consumeCurrentToken();
                
                $exp = new AssignmentExpression();
                $exp->setLeft($leftHandSideExpression);
                $exp->setOperator($token);
                $exp->setRight($this->assignmentExpression()); // 递归一下
            }
            else{
                throw new Exception(ERR_MSG_GRAMMAR_9, ERR_CODE_GRAMMAR_9);
            }
        }
        
        // 如果尝试LeftHandSideExpression，则尝试ConditionalExpression
        else{
            $exp = $this->conditionalExpression();
        }
        
        return $exp;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.12
     * 
     * ConditionalExpression : 
     *     LogicalORExpression 
     *     LogicalORExpression ? AssignmentExpression : AssignmentExpression 
     */
    private function conditionalExpression(){
        $exp = new ConditionalExpression();
        
        // logicalORExpression
        $logicalORExpression = $this->logicalORExpression();
        $exp->setTestExp($logicalORExpression);
        
        // 消耗掉?
        $punctuatorToken = $this->getCurrentToken();
        if( ($punctuatorToken->getTokenType()) != Token::Punctuator_Ask ){
            return $exp;
        }
        $this->consumeCurrentToken();
        
        // assignmentExpression
        $trueExp = $this->assignmentExpression();
        
        // 消耗掉:
        $punctuatorToken = $this->getCurrentToken();
        if( ($punctuatorToken->getTokenType()) != Token::Punctuator_Colon ){
            throw new Exception(ERR_MSG_GRAMMAR_6, ERR_CODE_GRAMMAR_6);
        }
        $this->consumeCurrentToken();
        
        // assignmentExpression
        $falseExp = $this->assignmentExpression();
        
        $exp->setTrueExp($trueExp);
        $exp->setFalseExp($falseExp);
        return $exp;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.11
     * 
     * LogicalORExpression  : 
     *     LogicalANDExpression 
     *     LogicalORExpression || LogicalANDExpression
     */
    private function logicalORExpression(){
        $exp = new LogicalORExpression();
        
        // logicalORExpression
        $logicalANDExpression = $this->logicalANDExpression();
        $exp->addExpression($logicalANDExpression);
        
        // 消耗掉||
        $punctuatorToken = $this->getCurrentToken();
        while ($punctuatorToken->getTokenType() == Token::Punctuator_OrOr){
            $this->consumeCurrentToken();
            
            // logicalORExpression
            $logicalANDExpression = $this->logicalANDExpression();
            $exp->addExpression($logicalANDExpression);
        }
        
        return $exp;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.11
     * 
     * LogicalANDExpression : 
     *     BitwiseORExpression  
     *     LogicalANDExpression && BitwiseORExpression
     */
    private function logicalANDExpression(){
        $exp = new LogicalANDExpression();
        
        // BitwiseORExpression
        $bitwiseORExpression = $this->bitwiseORExpression();
        $exp->addExpression($bitwiseORExpression);
        
        // 消耗掉&&
        $punctuatorToken = $this->getCurrentToken();
        while ($punctuatorToken->getTokenType() == Token::Punctuator_AndAnd){
            $this->consumeCurrentToken();
            
            // BitwiseORExpression
            $bitwiseORExpression = $this->bitwiseORExpression();
            $exp->addExpression($bitwiseORExpression);
        }
        
        return $exp;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.10
     */
    private function bitwiseORExpression(){
        $exp = new BitwiseORExpression();
        
        // BitwiseXORExpression
        $bitwiseXORExpression = $this->bitwiseXORExpression();
        $exp->addExpression($bitwiseXORExpression);
        
        // 消耗掉|
        $punctuatorToken = $this->getCurrentToken();
        while ($punctuatorToken->getTokenType() == Token::Punctuator_Or){
            $this->consumeCurrentToken();
            
            // BitwiseXORExpression
            $bitwiseXORExpression = $this->bitwiseXORExpression();
            $exp->addExpression($bitwiseXORExpression);
        }
        
        return $exp;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.10
     */
    private function bitwiseXORExpression(){
        $exp = new BitwiseXORExpression();
        
        // BitwiseANDExpression
        $bitwiseANDExpression = $this->bitwiseANDExpression();
        $exp->addExpression($bitwiseANDExpression);
        
        // 消耗掉^
        $punctuatorToken = $this->getCurrentToken();
        while ($punctuatorToken->getTokenType() == Token::Punctuator_ExclusiveOr){
            $this->consumeCurrentToken();
            
            // BitwiseANDExpression
            $bitwiseANDExpression = $this->bitwiseANDExpression();
            $exp->addExpression($bitwiseANDExpression);
        }
        
        return $exp;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.10
     */
    private function bitwiseANDExpression(){
        $exp = new BitwiseANDExpression();
        
        // EqualityExpression
        $equalityExpression = $this->equalityExpression();
        $exp->addExpression($equalityExpression);
        
        // 消耗掉&
        $punctuatorToken = $this->getCurrentToken();
        while ($punctuatorToken->getTokenType() == Token::Punctuator_And){
            $this->consumeCurrentToken();
            
            // EqualityExpression
            $equalityExpression = $this->equalityExpression();
            $exp->addExpression($equalityExpression);
        }
        
        return $exp;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.9
     * 
     * EqualityExpression : 
     *     RelationalExpression 
     *     EqualityExpression == RelationalExpression 
     *     EqualityExpression != RelationalExpression 
     *     EqualityExpression ===  RelationalExpression 
     *     EqualityExpression !==  RelationalExpression 
     */
    private function equalityExpression(){
        $exp = new EqualityExpression();
        
        // RelationalExpression
        $relationalExpression = $this->relationalExpression();
        $exp->setLeft($relationalExpression);
        
        // 消耗掉 ==, !=, ===, !==
        $punctuatorToken = $this->getCurrentToken();
        while ($punctuatorToken->getTokenType() == Token::Punctuator_EqualEqual
            || $punctuatorToken->getTokenType() == Token::Punctuator_NotEqual
            || $punctuatorToken->getTokenType() == Token::Punctuator_EqualEqualEqual
            || $punctuatorToken->getTokenType() == Token::Punctuator_NotEqualEqual
        ){
            $this->consumeCurrentToken();
            
            // RelationalExpression
            $relationalExpression = $this->relationalExpression();
            
            $exp2 = new EqualityExpression();
            $exp2->setLeft($exp);
            $exp2->setRight($relationalExpression);
            $exp2->setOperator($punctuatorToken);
            
            $exp = $exp2;
        }
        
        return $exp;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.8
     * 
     * RelationalExpression : 
     *     ShiftExpression 
     *     RelationalExpression < ShiftExpression 
     *     RelationalExpression > ShiftExpression 
     *     RelationalExpression <= ShiftExpression 
     *     RelationalExpression >= ShiftExpression 
     *     RelationalExpression instanceof  ShiftExpression 
     *     RelationalExpression in ShiftExpression 
     */
    private function relationalExpression(){
        $exp = new RelationalExpression();
        
        // ShiftExpression
        $shiftExpression = $this->shiftExpression();
        $exp->setLeft($shiftExpression);
        
        // 消耗掉 <, >, <=, >=, instanceof, in
        $token = $this->getCurrentToken();
        while ($token->getTokenType() == Token::Punctuator_Less
            || $token->getTokenType() == Token::Punctuator_More
            || $token->getTokenType() == Token::Punctuator_LessEqual
            || $token->getTokenType() == Token::Punctuator_MoreEqual
            || ($token->getTokenType() == Token::IdentifierName && $token->getTokenLiteral() == 'instanceof')
            || ($token->getTokenType() == Token::IdentifierName && $token->getTokenLiteral() == 'in')
        ){
            $this->consumeCurrentToken();
            
            // ShiftExpression
            $shiftExpression = $this->shiftExpression();
            
            $exp2 = new RelationalExpression();
            $exp2->setLeft($exp);
            $exp2->setRight($shiftExpression);
            $exp2->setOperator($token);
            
            $exp = $exp2;
        }
        
        return $exp;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.7
     * 
     * ShiftExpression : 
     *     AdditiveExpression  
     *     ShiftExpression << AdditiveExpression  
     *     ShiftExpression >> AdditiveExpression  
     *     ShiftExpression >>>  AdditiveExpression 
     */
    private function shiftExpression(){
        $exp = new ShiftExpression();
        
        // AdditiveExpression
        $additiveExpression = $this->additiveExpression();
        $exp->setLeft($additiveExpression);
        
        // 消耗掉 <<, >>, >>>
        $token = $this->getCurrentToken();
        while ($token->getTokenType() == Token::Punctuator_LessLess
            || $token->getTokenType() == Token::Punctuator_MoreMore
            || $token->getTokenType() == Token::Punctuator_MoreMoreMore
        ){
            $this->consumeCurrentToken();
            
            // AdditiveExpression
            $additiveExpression = $this->additiveExpression();
            
            $exp2 = new ShiftExpression();
            $exp2->setLeft($exp);
            $exp2->setRight($additiveExpression);
            $exp2->setOperator($token);
            
            $exp = $exp2;
        }
        
        return $exp;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.6
     * 
     * AdditiveExpression  : 
     *     MultiplicativeExpression 
     *     AdditiveExpression + MultiplicativeExpression 
     *     AdditiveExpression - MultiplicativeExpression
     */
    private function additiveExpression(){
        $exp = new AdditiveExpression();
        
        // MultiplicativeExpression
        $multiplicativeExpression = $this->multiplicativeExpression();
        $exp->setLeft($multiplicativeExpression);
        
        // 消耗掉 +, -
        $token = $this->getCurrentToken();
        while ($token->getTokenType() == Token::Punctuator_Add
            || $token->getTokenType() == Token::Punctuator_Minus
        ){
            $this->consumeCurrentToken();
            
            // MultiplicativeExpression
            $multiplicativeExpression = $this->multiplicativeExpression();
            
            $exp2 = new AdditiveExpression();
            $exp2->setLeft($exp);
            $exp2->setRight($multiplicativeExpression);
            $exp2->setOperator($token);
            
            $exp = $exp2;
        }
        
        return $exp;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.5
     * 
     * MultiplicativeExpression : 
     *     UnaryExpression 
     *     MultiplicativeExpression * UnaryExpression 
     *     MultiplicativeExpression / UnaryExpression 
     *     MultiplicativeExpression % UnaryExpression 
     */
    private function multiplicativeExpression(){
        $exp = new MultiplicativeExpression();
        
        // UnaryExpression
        $unaryExpression = $this->unaryExpression();
        $exp->setLeft($unaryExpression);
        
        // 消耗掉 *, /, %
        $token = $this->getCurrentToken();
        while ($token->getTokenType() == Token::Punctuator_Asterisk
            || $token->getTokenType() == Token::Punctuator_Division
            || $token->getTokenType() == Token::Punctuator_Percent
        ){
            $this->consumeCurrentToken();
            
            // UnaryExpression
            $unaryExpression = $this->unaryExpression();
            
            $exp2 = new MultiplicativeExpression();
            $exp2->setLeft($exp);
            $exp2->setRight($unaryExpression);
            $exp2->setOperator($token);
            
            $exp = $exp2;
        }
        
        return $exp;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.4
     * 
     * UnaryExpression : 
     *     PostfixExpression 
     *     delete UnaryExpression 
     *     void  UnaryExpression 
     *     typeof UnaryExpression  
     *     ++ UnaryExpression 
     *     -- UnaryExpression 
     *     + UnaryExpression 
     *     - UnaryExpression 
     *     ~ UnaryExpression 
     *     ! UnaryExpression 
     */
    private function unaryExpression(){
        $exp = NULL;
        
        // 消耗掉  delete, void, typeof, ++, --, +, -, ~, !
        $token = $this->getCurrentToken();
        while (($token->getTokenType() == Token::IdentifierName && $token->getTokenLiteral() == 'delete')
            || ($token->getTokenType() == Token::IdentifierName && $token->getTokenLiteral() == 'void')
            || ($token->getTokenType() == Token::IdentifierName && $token->getTokenLiteral() == 'typeof')
            || $token->getTokenType() == Token::Punctuator_AddAdd
            || $token->getTokenType() == Token::Punctuator_MinusMinus
            || $token->getTokenType() == Token::Punctuator_Add
            || $token->getTokenType() == Token::Punctuator_Minus
            || $token->getTokenType() == Token::Punctuator_BitNot
            || $token->getTokenType() == Token::Punctuator_Not
        ){
            $this->consumeCurrentToken();
            
            if($exp == NULL){
                $exp = new UnaryExpression();
                $exp->setOperator($token);
            }else{
                $exp2 = new UnaryExpression();
                $exp2->setOperator($token);
                $exp->setLeft($exp2);
                $exp = $exp2;
            }
        }
        
        $postfixExpression = $this->postfixExpression();
        if($exp == NULL){
            $exp = new UnaryExpression();
        }
        $exp->setLeft($postfixExpression);
        
        return $exp;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.3
     * 
     * PostfixExpression : 
     *     LeftHandSideExpression 
     *     LeftHandSideExpression [no LineTerminator here] ++
     *     LeftHandSideExpression [no LineTerminator here] --
     */
    private function postfixExpression(){
        $postfixExpression = new PostfixExpression();
        
        $leftHandSideExpression = $this->leftHandSideExpression();
        $postfixExpression->setLeft($leftHandSideExpression);
        
        //如果有++， --， 则吃掉
        $token = $this->getCurrentToken();
        if( $token->getTokenType() == Token::Punctuator_AddAdd ||
            $token->getTokenType() == Token::Punctuator_MinusMinus
        ){
            $this->consumeCurrentToken();
            $postfixExpression->setOperator($token);
        }
        
        return $postfixExpression;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.2
     * 
     * LeftHandSideExpression : 
     *     NewExpression 
     *     CallExpression 
     */
    private function leftHandSideExpression(){
        return $this->memberExpression();
    }
    
    private function memberExpression($allowCall = TRUE){
        //如果不是new开头
        $token = $this->getCurrentToken();
        if(!($token->getTokenType() == Token::IdentifierName && $token->getTokenLiteral() == 'new')){
            $exp = $this->primaryExpressionOrFunctionExpression();
        }
        else{
            $this->consumeCurrentToken();
            
            $exp = new NewExpression();
            $target = $this->memberExpression(FALSE);
            $exp->setTarget($target);
            
            // 遇到左小括号
            $token = $this->getCurrentToken();
            if($token->getTokenType() == Token::Punctuator_LeftParenthesis){
                $this->consumeCurrentToken();
                
                // 获取参数列表
                $args = $this->argumentList();
                $exp->setArgs($args);
                
                $token = $this->getCurrentToken();
                if($token->getTokenType() != Token::Punctuator_RightParenthesis){
                    throw new Exception(ERR_MSG_GRAMMAR_7, ERR_CODE_GRAMMAR_7);
                }
                $this->consumeCurrentToken();
            }
        }
        
        $tail = $this->memberExpressionTail($allowCall, $exp);
        return tail;
    }
    
    private function memberExpressionTail($allowCall = TRUE, $target){
        for (;;) {
            $token = $this->getCurrentToken();
            
            // 点
            if($token->getTokenType() == Token::Punctuator_Dot){
                $myExp = $this->propertyAccess($target);
            }
            // 中括号
            else if($token->getTokenType() == Token::Punctuator_LeftSquareBrace){
                $this->consumeCurrentToken();
                $exp = $this->expression();
                $token = $this->getCurrentToken();
                if($token->getTokenType() != Token::Punctuator_RightSquareBrace){
                    throw new Exception(ERR_MSG_GRAMMAR_8, ERR_CODE_GRAMMAR_8);
                }
                $this->consumeCurrentToken();
                
                $myExp = new GetElementExpression();
                $myExp->setTarget($target);
                $myExp->setExp($exp);
            }
            // 小括号
            else if($token->getTokenType() == Token::Punctuator_LeftParenthesis){
                $this->consumeCurrentToken();
                
                // 获取参数列表
                $args = $this->argumentList();
                
                $token = $this->getCurrentToken();
                if($token->getTokenType() != Token::Punctuator_RightParenthesis){
                    throw new Exception(ERR_MSG_GRAMMAR_8, ERR_CODE_GRAMMAR_8);
                }
                $this->consumeCurrentToken();
                
                $myExp = new CallFunctionExpression();
                $myExp->setTarget($target);
                $myExp->setArgs($args);
            }
            $target = $myExp;
        }
        
        return $target;
    }
    
    private function primaryExpressionOrFunctionExpression(){
        $token = $this->getCurrentToken();
        $tokenType = $token->getTokenType();
        $tokenLiteral = $token->getTokenLiteral();
        
        if($tokenType == Token::IdentifierName && $tokenLiteral == 'function'){
            $node = $this->functionExpression();
        }
        else{
            $node = $this->primaryExpression();
        }
        
        return $node;
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 13
     * 
     * FunctionExpression : 
     *     function  [Identifier] ( [FormalParameterList] )  { 
     *         FunctionBody 
     *     } 
     */
    private function functionExpression(){
        return $this->functionDeclaration();
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.1
     * 
     * PrimaryExpression : 
     *     this 
     *     Identifier 
     *     Literal 
     *     ArrayLiteral 
     *     ObjectLiteral 
     *     ( Expression  ) 
     */
    private function primaryExpression(){
        $token = $this->getCurrentToken();
        $tokenType = $token->getTokenType();
        $tokenLiteral = $token->getTokenLiteral();
        
        if($tokenType == Token::IdentifierName && $tokenLiteral == 'this'){
            return $this->createKeywordNode($token);
        }
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'true'){
            return $this->createKeywordNode($token);
        }
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'false'){
            return $this->createKeywordNode($token);
        }
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'null'){
            return $this->createKeywordNode($token);
        }
        else if($tokenType == Token::IdentifierName && !ReservedWord::isReservedWord($tokenLiteral) ){
            return $this->createIdNode($token);
        }
        else if($tokenType == Token::StringLiteral){
            return $this->createStringNode($token);
        }
        else if($tokenType == Token::NumericLiteral){
            return $this->createNumberNode($token);
        }
        else if($tokenType == Token::Punctuator_Division){
            // 正则表达式
            // TO-DO
        }
        else if($tokenType == Token::Punctuator_LeftSquareBrace){
            return $this->arrayLiteral();
        }
        else if($tokenType == Token::Punctuator_LeftBrace){
            return $this->objectLiteral();
        }
        else if($tokenType == Token::Punctuator_LeftParenthesis){
            return $this->parenthesesExpression();
        }
        else{
            throw new Exception(ERR_MSG_GRAMMAR_10, ERR_CODE_GRAMMAR_10);
        }
    }
    
    /**
     * 
     * @see ECMA-262 5rd chapter 11.1.4
     * 
     * ArrayLiteral : 
     *     [ Elision opt ] 
     *     [ ElementList  ] 
     *     [ ElementList ,  Elisionopt ] 
     */
    private function arrayLiteral(){
        $token = $this->getCurrentToken();
        $tokenType = $token->getTokenType();
        $tokenLiteral = $token->getTokenLiteral();
        
        if($tokenType != Token::Punctuator_LeftSquareBrace){
            throw new Exception(ERR_MSG_GRAMMAR_11, ERR_CODE_GRAMMAR_11); 
        }
        $this->consumeCurrentToken();
        
        $arr = new ArrayNode();
        $lastTokenIsComma = TRUE;
        for(;;){
            $token = $this->getCurrentToken();
            $tokenType = $token->getTokenType();
            $tokenLiteral = $token->getTokenLiteral();
            
            if($tokenType == Token::Punctuator_RightSquareBrace){
                break;
            }
            else if($tokenType == Token::Punctuator_Comma){
                if( $lastTokenIsComma ){
                    $arr->addElement(new EmptyStatementNode());
                }else{
                    $lastTokenIsComma = TRUE;
                }
            }
            else{
                $lastTokenIsComma = FALSE;
                $exp = $this->assignmentExpression();
                $arr->addElement($exp);
            }
        }
        
        return $arr;
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    /**
     * @see ECMA-262 5rd chapter 12.6
     */
    private function iterationStatement(){
        $currentToken = $this->getCurrentToken();
        $tokenType = $currentToken->getTokenType();
        $tokenLiteral = $currentToken->getTokenLiteral();
        if($tokenType == Token::IdentifierName && $tokenLiteral == 'do'){
            $statement = $this->parseDoWhile();
        }
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'while'){
            $statement = $this->parseWhile();
        }
        else if($tokenType == Token::IdentifierName && $tokenLiteral == 'for'){
            $statement = $this->parseFor();
        }
        
        return $statement;
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    private function createIdNode($token){
        $type = $token->getTokenType();
        $literal = $token->getTokenLiteral();
        $lineNumber = $token->getLineNumber();
        $position = $token->getTokenPosition();
        
        $node = new IdNode();
        $node->idLiteral = $literal;
        $node->lineNumber = $lineNumber;
        $node->position = $position;
        
        return $node;
    }
    
    private function createKeywordNode($token){
        $type = $token->getTokenType();
        $literal = $token->getTokenLiteral();
        $lineNumber = $token->getLineNumber();
        $position = $token->getTokenPosition();
        
        $node = new KeywordNode();
        $node->idLiteral = $literal;
        $node->lineNumber = $lineNumber;
        $node->position = $position;
        
        return $node;
    }
    
    private function createStringNode($token){
        $type = $token->getTokenType();
        $literal = $token->getTokenLiteral();
        $lineNumber = $token->getLineNumber();
        $position = $token->getTokenPosition();
        
        $node = new StringNode();
        $node->value = $literal;
        $node->lineNumber = $lineNumber;
        $node->position = $position;
        
        return $node;
    }
    
    private function createNumberNode($token){
        $type = $token->getTokenType();
        $literal = $token->getTokenLiteral();
        $lineNumber = $token->getLineNumber();
        $position = $token->getTokenPosition();
        
        $node = new NumberNode();
        $node->value = $literal;
        $node->lineNumber = $lineNumber;
        $node->position = $position;
        
        return $node;
    }
    
    private function createFunctionNode($functionName,$functionParamList,$functionBody){
        $functionNode = new FunctionNode();
        $functionNode->functionName = $functionName;
        $functionNode->functionParamList = $functionParamList;
        $functionNode->functionBody = $functionBody;
        
        return $functionNode;
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    private function getCurrentToken(){
        return $this->tokenList[$this->tokenIndex];
    }
    
    private function getNextToken($n=1){
        $index = $this->tokenIndex + $n;
        return $this->tokenList[$index];
    }
    
    private function consumeCurrentToken(){
        $this->tokenIndex ++ ;
    }
}